//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 
//
// 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 
//
// 示例 2： 
//
// 
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// Related Topics 并查集 数组 哈希表 👍 1926 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author ldltd
 * @date 2023-12-20 21:15:58
 * @description 128.最长连续序列
 */
public class LongestConsecutiveSequence{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new LongestConsecutiveSequence().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestConsecutive2(int[] nums) {
			//hash
		Set<Integer> set=new HashSet<>();
		for (int num : nums) {
			set.add(num);
		}
		int res=0;
		//如果没有比他更小的数，就从他开始找最长的
		for (Integer integer : set) {
			if(!set.contains(integer-1)){
				int l=integer;
				while (set.contains(l+1)){
					l=l+1;
				}
				res=Math.max(res,l-integer+1);
			}
		}
		return res;
    }

	//哈希表记录连续区间长度，每次检查左右两边的数是否在表中，在就跳过，不在就更新左右区间和结果
	public int longestConsecutive1(int[] nums) {
		Map<Integer,Integer> map=new HashMap<>();
		int res=0;
		for (int num : nums) {
			if(!map.containsKey(num)){
				int l=map.getOrDefault(num-1,0);
				int r=map.getOrDefault(num+1,0);
				int t=l+r+1;
				res=Math.max(res,t);
				// 这里一次性标记了三个数，l m r,其中l,m 之间的数不会再被访问，只需要关注边界即可
				map.put(num-l,t);
				map.put(num,t);
				map.put(num+r,t);
			}
		}
		return res;
	}
	//并查集

	class UnionFind{
		//记录每个结点父结点
		private Map<Integer,Integer> parent;

		public UnionFind(int []nums){
			parent=new HashMap<>();
			for (int num : nums) {
				//先默认每个的父结点是自己
				parent.put(num,num);
			}
		}

		//寻找父结点，并且路径压缩
		public Integer find(int x){
			//nums 不包含x
			if(!parent.containsKey(x)){
				return null;
			}
			//遍历找x父结点
			while (x!=parent.get(x)){
				parent.put(x,parent.get(parent.get(x)));
				x=parent.get(x);
			}
			return x;
		}

		//合并两个连同分量，本题中将num并入num+1区间中
		public void union(int x,int y){
			int rootX=find(x);
			int rootY=find(y);
			if(rootY==rootX){
				return;
			}
			parent.put(rootX,rootY);
		}
	}

	public int longestConsecutive(int[] nums) {
		UnionFind uf=new UnionFind(nums);
		int res=0;
		for (int num : nums) {
			//如果num+1存在，加入num+1集合中
			if(uf.find(num+1)!=null){
				uf.union(num,num+1);
			}
		}
		for (int num : nums) {
			//找到num的最远连续右边界
			int r=uf.find(num);
			res=Math.max(res,r-num+1);
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
